{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "import random\n",
    "import time\n",
    "from bisect import bisect_left\n",
    "from enum import Enum\n",
    "from math import exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _mutate_custom(parent, custom_mutate, get_fitness):\n",
    "    childGenes = parent.Genes[:]\n",
    "    custom_mutate(childGenes)\n",
    "    fitness = get_fitness(childGenes)\n",
    "    return Chromosome(childGenes, fitness, Strategies.Mutate)\n",
    "\n",
    "\n",
    "def _crossover(parentGenes, index, parents, get_fitness, crossover, mutate,\n",
    "               generate_parent):\n",
    "    donorIndex = random.randrange(0, len(parents))\n",
    "    if donorIndex == index:\n",
    "        donorIndex = (donorIndex + 1) % len(parents)\n",
    "    childGenes = crossover(parentGenes, parents[donorIndex].Genes)\n",
    "    if childGenes is None:\n",
    "        # parent and donor are indistinguishable\n",
    "        parents[donorIndex] = generate_parent()\n",
    "        return mutate(parents[index])\n",
    "    fitness = get_fitness(childGenes)\n",
    "    return Chromosome(childGenes, fitness, Strategies.Crossover)\n",
    "\n",
    "\n",
    "def get_best(get_fitness, targetLen, optimalFitness, geneSet, display,\n",
    "             custom_mutate=None, custom_create=None, maxAge=None, poolSize=1,\n",
    "             crossover=None, maxSeconds=None):\n",
    "    if custom_mutate is None:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate(parent, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate_custom(parent, custom_mutate, get_fitness)\n",
    "\n",
    "    if custom_create is None:\n",
    "        def fnGenerateParent():\n",
    "            return _generate_parent(targetLen, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnGenerateParent():\n",
    "            genes = custom_create()\n",
    "            return Chromosome(genes, get_fitness(genes), Strategies.Create)\n",
    "\n",
    "    strategyLookup = {\n",
    "        Strategies.Create: lambda p, i, o: fnGenerateParent(),\n",
    "        Strategies.Mutate: lambda p, i, o: fnMutate(p),\n",
    "        Strategies.Crossover: lambda p, i, o:\n",
    "        _crossover(p.Genes, i, o, get_fitness, crossover, fnMutate,\n",
    "                   fnGenerateParent)\n",
    "    }\n",
    "\n",
    "    usedStrategies = [strategyLookup[Strategies.Mutate]]\n",
    "    if crossover is not None:\n",
    "        usedStrategies.append(strategyLookup[Strategies.Crossover])\n",
    "\n",
    "        def fnNewChild(parent, index, parents):\n",
    "            return random.choice(usedStrategies)(parent, index, parents)\n",
    "    else:\n",
    "        def fnNewChild(parent, index, parents):\n",
    "            return fnMutate(parent)\n",
    "\n",
    "    for timedOut, improvement in \\\n",
    "            _get_improvement(fnNewChild, fnGenerateParent, maxAge, poolSize,\n",
    "                             maxSeconds):\n",
    "        if timedOut:\n",
    "            return improvement\n",
    "        display(improvement)\n",
    "        f = strategyLookup[improvement.Strategy]\n",
    "        usedStrategies.append(f)\n",
    "        if not optimalFitness > improvement.Fitness:\n",
    "            return improvement\n",
    "\n",
    "\n",
    "def _get_improvement(new_child, generate_parent, maxAge, poolSize, maxSeconds):\n",
    "    startTime = time.time()\n",
    "    bestParent = generate_parent()\n",
    "    yield maxSeconds is not None and time.time() \\\n",
    "          - startTime > maxSeconds, bestParent\n",
    "    parents = [bestParent]\n",
    "    historicalFitnesses = [bestParent.Fitness]\n",
    "    for _ in range(poolSize - 1):\n",
    "        parent = generate_parent()\n",
    "        if maxSeconds is not None and time.time() - startTime > maxSeconds:\n",
    "            yield True, parent\n",
    "        if parent.Fitness > bestParent.Fitness:\n",
    "            yield False, parent\n",
    "            bestParent = parent\n",
    "            historicalFitnesses.append(parent.Fitness)\n",
    "        parents.append(parent)\n",
    "    lastParentIndex = poolSize - 1\n",
    "    pindex = 1\n",
    "    while True:\n",
    "        if maxSeconds is not None and time.time() - startTime > maxSeconds:\n",
    "            yield True, bestParent\n",
    "        pindex = pindex - 1 if pindex > 0 else lastParentIndex\n",
    "        parent = parents[pindex]\n",
    "        child = new_child(parent, pindex, parents)\n",
    "        if parent.Fitness > child.Fitness:\n",
    "            if maxAge is None:\n",
    "                continue\n",
    "            parent.Age += 1\n",
    "            if maxAge > parent.Age:\n",
    "                continue\n",
    "            index = bisect_left(historicalFitnesses, child.Fitness, 0,\n",
    "                                len(historicalFitnesses))\n",
    "            proportionSimilar = index / len(historicalFitnesses)\n",
    "            if random.random() < exp(-proportionSimilar):\n",
    "                parents[pindex] = child\n",
    "                continue\n",
    "            bestParent.Age = 0\n",
    "            parents[pindex] = bestParent\n",
    "            continue\n",
    "        if not child.Fitness > parent.Fitness:\n",
    "            # same fitness\n",
    "            child.Age = parent.Age + 1\n",
    "            parents[pindex] = child\n",
    "            continue\n",
    "        child.Age = 0\n",
    "        parents[pindex] = child\n",
    "        if child.Fitness > bestParent.Fitness:\n",
    "            bestParent = child\n",
    "            yield False, bestParent\n",
    "            historicalFitnesses.append(bestParent.Fitness)\n",
    "\n",
    "\n",
    "class Chromosome:\n",
    "    def __init__(self, genes, fitness, strategy):\n",
    "        self.Genes = genes\n",
    "        self.Fitness = fitness\n",
    "        self.Strategy = strategy\n",
    "        self.Age = 0\n",
    "\n",
    "\n",
    "class Strategies(Enum):\n",
    "    Create = 0,\n",
    "    Mutate = 1,\n",
    "    Crossover = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate(genes, prioritizedOperations):\n",
    "    equation = genes[:]\n",
    "    for operationSet in prioritizedOperations:\n",
    "        iOffset = 0\n",
    "        for i in range(1, len(equation), 2):\n",
    "            i += iOffset\n",
    "            opToken = equation[i]\n",
    "            if opToken in operationSet:\n",
    "                leftOperand = equation[i - 1]\n",
    "                rightOperand = equation[i + 1]\n",
    "                equation[i - 1] = operationSet[opToken](leftOperand,\n",
    "                                                        rightOperand)\n",
    "                del equation[i + 1]\n",
    "                del equation[i]\n",
    "                iOffset += -2\n",
    "    return equation[0]\n",
    "\n",
    "\n",
    "def add(a, b):\n",
    "    return a + b\n",
    "\n",
    "\n",
    "def subtract(a, b):\n",
    "    return a - b\n",
    "\n",
    "\n",
    "def multiply(a, b):\n",
    "    return a * b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitness(genes, expectedTotal, fnEvaluate):\n",
    "    result = fnEvaluate(genes)\n",
    "\n",
    "    if result != expectedTotal:\n",
    "        fitness = expectedTotal - abs(result - expectedTotal)\n",
    "    else:\n",
    "        fitness = 1000 - len(genes)\n",
    "\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def display(candidate, startTime):\n",
    "    timeDiff = datetime.datetime.now() - startTime\n",
    "    print(\"{}\\t{}\\t{}\".format(\n",
    "        (' '.join(map(str, [i for i in candidate.Genes]))),\n",
    "        candidate.Fitness,\n",
    "        timeDiff))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create(numbers, operations, minNumbers, maxNumbers):\n",
    "    genes = [random.choice(numbers)]\n",
    "    count = random.randint(minNumbers, 1 + maxNumbers)\n",
    "    while count > 1:\n",
    "        count -= 1\n",
    "        genes.append(random.choice(operations))\n",
    "        genes.append(random.choice(numbers))\n",
    "    return genes\n",
    "\n",
    "\n",
    "def mutate(genes, numbers, operations, minNumbers, maxNumbers,\n",
    "           fnGetFitness):\n",
    "    count = random.randint(1, 10)\n",
    "    initialFitness = fnGetFitness(genes)\n",
    "    while count > 0:\n",
    "        count -= 1\n",
    "        if fnGetFitness(genes) > initialFitness:\n",
    "            return\n",
    "        numberCount = (1 + len(genes)) / 2\n",
    "        adding = numberCount < maxNumbers and random.randint(0, 100) == 0\n",
    "        if adding:\n",
    "            genes.append(random.choice(operations))\n",
    "            genes.append(random.choice(numbers))\n",
    "            continue\n",
    "\n",
    "        removing = numberCount > minNumbers and random.randint(0, 20) == 0\n",
    "        if removing:\n",
    "            index = random.randrange(0, len(genes) - 1)\n",
    "            del genes[index]\n",
    "            del genes[index]\n",
    "            continue\n",
    "\n",
    "        index = random.randrange(0, len(genes))\n",
    "        genes[index] = random.choice(operations) \\\n",
    "            if (index & 1) == 1 else random.choice(numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(operations, prioritizedOperations,\n",
    "              optimalLengthSolution):\n",
    "    numbers = [1, 2, 3, 4, 5, 6, 7]\n",
    "    expectedTotal = evaluate(optimalLengthSolution,\n",
    "                                 prioritizedOperations)\n",
    "    minNumbers = (1 + len(optimalLengthSolution)) / 2\n",
    "    maxNumbers = 6 * minNumbers\n",
    "    startTime = datetime.datetime.now()\n",
    "\n",
    "    def fnDisplay(candidate):\n",
    "        display(candidate, startTime)\n",
    "\n",
    "    def fnEvaluate(genes):\n",
    "        return evaluate(genes, prioritizedOperations)\n",
    "\n",
    "    def fnGetFitness(genes):\n",
    "        return get_fitness(genes, expectedTotal, fnEvaluate)\n",
    "\n",
    "    def fnCreate():\n",
    "        return create(numbers, operations, minNumbers, maxNumbers)\n",
    "\n",
    "    def fnMutate(child):\n",
    "        mutate(child, numbers, operations, minNumbers, maxNumbers,\n",
    "                   fnGetFitness)\n",
    "\n",
    "    optimalFitness = fnGetFitness(optimalLengthSolution)\n",
    "    best = get_best(fnGetFitness, None, optimalFitness, None,\n",
    "                                fnDisplay, fnMutate, fnCreate, maxAge=50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_addition():\n",
    "    operations = ['+', '-']\n",
    "    prioritizedOperations = [{'+': add,\n",
    "                                  '-': subtract}]\n",
    "    optimalLengthSolution = [7, '+', 7, '+', 7, '+', 7, '+', 7, '-', 6]\n",
    "    solve(operations, prioritizedOperations, optimalLengthSolution)\n",
    "\n",
    "def test_multiplication():\n",
    "    operations = ['+', '-', '*']\n",
    "    prioritizedOperations = [{'*': multiply},\n",
    "                                 {'+': add,\n",
    "                                  '-': subtract}]\n",
    "    optimalLengthSolution = [6, '*', 3, '*', 3, '*', 6, '-', 7]\n",
    "    solve(operations, prioritizedOperations, optimalLengthSolution)\n",
    "\n",
    "def test_exponent():\n",
    "    operations = ['^', '+', '-', '*']\n",
    "    prioritizedOperations = [{'^': lambda a, b: a ** b},\n",
    "                                 {'*': multiply},\n",
    "                                 {'+': add,\n",
    "                                  '-': subtract}]\n",
    "    optimalLengthSolution = [6, '^', 3, '*', 2, '-', 5]\n",
    "    solve(operations, prioritizedOperations, optimalLengthSolution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 + 4 - 3 + 2 - 5 - 5 - 2 - 1 + 3 - 1 + 2 - 4 + 3 + 6 - 4\t1\t0:00:00\n",
      "6 + 4 - 3 + 2 - 5 - 5 - 2 - 1 + 5 - 1 + 2 - 4 + 3 + 6 - 4\t3\t0:00:00.000988\n",
      "6 + 4 - 3 + 2 - 5 - 5 - 2 - 1 + 5 - 1 + 2 + 4 + 3 + 6 - 4\t11\t0:00:00.000988\n",
      "6 + 4 - 3 + 2 - 4 - 5 - 2 - 1 + 5 - 1 + 2 + 4 + 3 + 6 - 4\t12\t0:00:00.000988\n",
      "6 + 4 - 3 + 2 - 4 + 5 - 2 - 6 + 5 - 1 + 1 + 2 + 3 + 6 - 4\t14\t0:00:00.000988\n",
      "6 + 4 - 3 + 2 - 4 + 5 - 2 - 6 + 5 + 1 + 1 + 2 + 3 + 6 - 4\t16\t0:00:00.000988\n",
      "6 + 4 - 3 + 2 - 4 + 5 - 2 - 6 + 5 + 1 + 1 + 2 + 3 + 6\t20\t0:00:00.001981\n",
      "6 + 4 - 3 + 2 + 4 + 2 - 2 - 6 + 5 + 1 + 1 + 2 + 2 + 6\t24\t0:00:00.001981\n",
      "6 + 4 - 3 + 4 + 4 + 2 - 2 - 6 + 5 + 1 + 1 + 2 + 2 + 6\t26\t0:00:00.001981\n",
      "6 + 4 - 3 + 4 + 7 + 2 - 2 - 6 + 5 + 1 + 1 + 2 + 1 + 6\t28\t0:00:00.002972\n",
      "6 + 2 - 3 + 4 + 7 + 2 - 1 - 4 + 5 + 1 + 1 + 2 + 1 + 6\t973\t0:00:00.002972\n",
      "6 + 2 - 3 + 4 + 7 + 2 - 1 - 4 + 5 - 1 + 3 + 3 + 6\t975\t0:00:00.003969\n",
      "6 + 2 - 3 + 4 + 7 + 1 - 4 + 5 - 1 + 3 + 3 + 6\t977\t0:00:00.004968\n",
      "6 + 6 - 3 + 1 + 3 + 7 - 4 + 3 - 1 + 5 + 6\t979\t0:00:00.013944\n",
      "6 + 3 + 1 + 3 + 7 - 7 + 3 + 3 + 4 + 6\t981\t0:00:00.016967\n",
      "6 + 6 + 1 + 3 - 4 + 6 + 3 + 7 + 1\t983\t0:00:00.026540\n",
      "6 + 6 + 5 + 3 - 4 + 1 + 7 + 5\t985\t0:00:00.026540\n",
      "6 + 7 + 7 - 7 + 7 + 7 + 2\t987\t0:00:00.034520\n",
      "7 + 6 + 5 + 3 + 5 + 3\t989\t0:00:00.052504\n"
     ]
    }
   ],
   "source": [
    "test_addition()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 * 1 * 5 - 5 + 3 * 7\t31\t0:00:00\n",
      "4 * 1 * 5 - 5 + 3 * 7\t36\t0:00:00.001001\n",
      "4 * 1 * 6 - 5 + 3 * 7\t40\t0:00:00.001001\n",
      "4 * 1 * 6 - 5 + 5 * 7\t54\t0:00:00.002003\n",
      "4 * 4 * 6 - 5 + 5 * 7\t126\t0:00:00.002003\n",
      "4 * 4 * 6 * 5 + 5 * 5\t129\t0:00:00.002993\n",
      "4 * 4 * 6 * 5 + 6 - 5\t153\t0:00:00.002993\n",
      "4 * 4 * 6 * 5 + 6 - 5 * 7\t183\t0:00:00.002993\n",
      "4 * 3 * 6 * 5 + 6 - 5 * 7\t303\t0:00:00.003991\n",
      "4 * 3 * 6 * 4 + 6 + 5 * 7\t305\t0:00:00.003991\n",
      "4 * 3 * 6 * 4 + 6 * 5 - 7\t311\t0:00:00.003991\n",
      "4 * 3 * 6 * 4 + 7 * 5 - 7\t316\t0:00:00.004987\n",
      "4 * 3 * 6 * 4 + 7 * 5 - 6\t987\t0:00:00.004987\n",
      "5 + 6 * 7 * 7 + 6 * 3\t989\t0:00:00.180557\n",
      "2 + 7 * 5 * 3 * 3\t991\t0:00:00.221408\n"
     ]
    }
   ],
   "source": [
    "test_multiplication()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 * 5 + 2 ^ 1 * 3 * 4 ^ 6 * 4 ^ 4 ^ 6 + 3 * 1 * 1 * 5 - 7 * 4\t-6917529027641081019\t0:00:00\n",
      "6 * 5 + 2 ^ 1 * 3 * 4 ^ 6 * 4 ^ 4 ^ 3 + 3 * 1 * 1 * 5 - 3 * 4\t-412316859595\t0:00:00.000998\n",
      "6 * 5 + 2 ^ 1 * 3 ^ 6 * 4 ^ 4 ^ 3 + 3 * 1 * 1 * 5 - 3 * 4\t-24461180107\t0:00:00.000998\n",
      "6 * 5 + 2 ^ 1 * 3 ^ 6 * 4 ^ 4 * 3 + 3 * 1 * 1 * 5 - 3 * 4\t-1118923\t0:00:00.000998\n",
      "6 * 5 + 2 + 1 * 3 ^ 6 * 4 ^ 4 * 3 + 3 * 1 * 1 * 5 - 1 * 4\t-559061\t0:00:00.002026\n",
      "6 * 5 + 2 + 1 * 3 ^ 6 * 2 ^ 4 * 3 + 3 * 1 * 1 * 5 - 1 * 4\t-34181\t0:00:00.002026\n",
      "6 + 2 + 1 * 3 ^ 6 * 2 ^ 4 * 3 + 3 * 1 * 1 * 5 - 1 * 4\t-34157\t0:00:00.002026\n",
      "6 + 2 + 1 * 3 ^ 6 * 2 - 4 * 7 + 3 * 1 * 1 * 5 - 1 ^ 4\t-598\t0:00:00.002026\n",
      "6 + 2 + 1 * 3 - 6 * 2 - 4 * 4 + 3 * 1 * 1 * 5 - 1 ^ 4\t-3\t0:00:00.002998\n",
      "6 + 2 + 1 * 3 - 6 * 2 - 4 * 4 + 3 * 1 * 6 * 5 - 1 ^ 4\t72\t0:00:00.002998\n",
      "6 + 2 + 1 * 3 - 6 * 2 - 4 * 4 + 5 * 1 * 6 * 5 - 1 ^ 4\t132\t0:00:00.002998\n",
      "6 + 2 + 1 * 3 - 6 * 2 - 4 * 4 + 5 * 7 * 6 * 5 - 5 ^ 4\t408\t0:00:00.002998\n",
      "6 + 2 + 1 * 3 - 6 * 2 + 4 * 4 + 5 * 7 * 6 * 5 - 5 ^ 4\t414\t0:00:00.002998\n",
      "6 + 2 + 1 * 3 - 6 * 2 + 4 + 4 + 5 * 7 * 6 * 5 - 5 ^ 4\t422\t0:00:00.002998\n",
      "6 + 2 + 1 * 3 - 6 * 2 + 4 - 4 + 5 * 7 * 6 * 5 - 5 ^ 4\t424\t0:00:00.003988\n",
      "6 + 2 + 1 * 3 - 6 * 2 + 6 - 4 + 5 * 7 * 6 * 5 - 5 ^ 4\t426\t0:00:00.005983\n",
      "6 + 2 + 1 * 3 - 6 * 2 + 6 - 3 + 5 * 7 * 6 * 5 - 5 ^ 4\t973\t0:00:00.005983\n",
      "3 + 2 ^ 6 + 7 * 7 + 7 + 2 + 7 * 7 * 6 + 4 + 4\t977\t0:00:00.036901\n",
      "6 + 2 ^ 6 + 7 * 7 * 2 + 6 * 7 * 6 + 7\t981\t0:00:00.046873\n",
      "3 ^ 5 + 4 * 4 * 2 * 6 - 7 - 1\t985\t0:00:00.087777\n",
      "3 + 3 * 7 * 5 * 4 + 1 * 4\t987\t0:00:00.103727\n",
      "3 * 7 * 4 * 5 + 7\t991\t0:00:00.197002\n",
      "6 ^ 3 * 2 - 5\t993\t0:00:00.520614\n"
     ]
    }
   ],
   "source": [
    "test_exponent()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
